package special;

import java.util.Arrays;

class TreeAncestor {

    private int[][] pa;

    public TreeAncestor(int n, int[] parent) {
        int m = 32 - Integer.numberOfLeadingZeros(n);
        pa = new int[n][m];
        for (int i = 0; i < n; i++) {
            pa[i][0] = parent[i];
        }
        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                int p = pa[x][i];
                pa[x][i + 1] = p < 0 ? -1 : pa[p][i];
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
        if (k == 0)
            return node;
        int loc = 0;
        while ((1 << loc) <= k){
            loc++;
        }
        loc--;
        if (pa[node][loc] == -1)
            return -1;
        return getKthAncestor(pa[node][loc], k -(1 << loc));
    }
}